package com.hfb.mashibing.alip8.datastructure.heap.binaryheap;

import java.util.Arrays;

/**
 * 堆排序
 * 堆排序代码实现
 * 要求：给你一个数组{4,6,8,5,9}，要求使用堆排序法，将数组升序排序。
 * 代码实现：看老师演示：
 * 说明：
 * 1)堆排序不是很好理解，可以通过Debug帮助大家理解堆排序
 * 2)堆排序的速度非常快，在我的机器上8百万数据3秒左右。
 *
 *
 * 最大堆（大顶堆）和 最小堆（小顶堆）
 * 基本思想 ：
 *      将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点；
 *      将其与末尾元素进行交换，此时末尾就为最大值，可称为有序区。
 *      然后将剩余 n-1个元素重新构造成一个堆，估且称为堆区(未排序)，
 *      这样会得到 n个元素的次小值（将开始的第一个堆顶也算进去了，所以还是n个数）。
 *      重复执行，有序区从:1—>n，堆区：n–>0，便能得到一个有序序列了
 *
 * 复杂度：
 *      对O(n)级别个非叶子节点进行堆调整操作 O(logn)，时间复杂度O(nlogn)；
 *      之后每一次堆调整操作确定一个数的次序，时间复杂度O(nlogn)；合起来时间复杂度O(nlogn)。
 *      额外空间开销出在调整堆过程，根节点下移交换时一个暂存空间，空间复杂度O(1)；
 *      堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，
 *      平均时间复杂度均为:O(nlogn)，是不稳定排序！
 *
 * 一般升序 用 大顶堆，降序 用 小顶堆
 */
public class heapSort {

    public static void main(String[] args) {
        // 升序排列
//        int[] arr = {4, 6, 8, 5, 9};
        int[] arr = {4, 6, 8, 5, 9,-1, 90,89,56,-999};
        heapSort(arr);
    }
    public static void heapSort(int[] arr){
        System.out.printf("堆排序前:%s\n", Arrays.toString(arr));
        int temp = 0;
        // 把数组构建成堆，格局升序需求选择大顶堆 or 小顶堆
        for (int i = arr.length/2-1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        System.out.printf("构建成堆(for:%s):%s\n", arr.length/2-1,Arrays.toString(arr));

        // 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
        // 重新调整结构，使其满足题目,继续交换堆顶元素与当前末尾元素反复调整+交换 直到整个徐磊有序
        for (int j = arr.length-1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.printf("堆排序后(for:%s):%s\n", arr.length-1,Arrays.toString(arr));
    }

    /** 将一个数组（二叉树），调整为一个大顶堆
     *  完成以 i 为非叶子节点的数组调整为大顶堆
     *  例如：
     *      arr = {4, 6, 8, 5, 9};
     *      i = 1; => adjustHeap 得到 {4, 9, 8, 5, 6};
     *      i = 0; => adjustHeap 得到 {9, 6, 8, 5, 4};
     *
     * @param arr 待调整的数组
     * @param i 非叶子节点在数组中的索引
     * @param len 数组元素的长度
     */
    public static void adjustHeap(int[] arr, int i, int len){
        int temp = arr[i];
        // 1. k=i*2+1 是 i 节点的左子节点
        for (int k = i*2+1; k < len; k = k*2+1) {
            if(k+1<len && arr[k]<arr[k+1]){    // 左子节点的值小于右子节点
                k++;// k 指向右子节点
            }
            if(arr[k] > temp){// 如果子节点大于父节点
                arr[i] = arr[k];// 把大的值赋值给当前节点
                i = k;// i 指向 k，继续循环比较
            } else {
                break;
            }
        }
        // 把 temp 放到调整后的位置
        arr[i] = temp;
    }
}
